#include <iostream>
#include <deque>
#include <queue>
#include <vector>
#include <time.h>
#include <algorithm>

using namespace std;

void Efficient1()
{
	srand(time(0));
	const int N = 100000;
	deque<int> dq;
	vector<int> v;

	for (int i = 0; i < N; i++)
	{
		auto e = rand() + i;
		v.push_back(e);
		dq.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	sort(dq.begin(), dq.end());
	int end2 = clock();

	printf("vector:%d  deque:%d\n", end1 - begin1, end2 - begin2);
}


void Efficient2()
{
	srand(time(0));
	const int N = 100000;
	deque<int>  dq1;
	deque<int> dq2;

	for (int i = 0; i < N; i++)
	{
		auto e = rand() + i;
		dq1.push_back(e);
		dq2.push_back(e);
	}

	int begin1 = clock();
	sort(dq1.begin(), dq1.end());
	int end1 = clock();

	int begin2 = clock();
	vector<int> v(dq2.begin(), dq2.end());
	sort(v.begin(), v.end());
	dq2.assign(v.begin(), v.end());
	int end2 = clock();

	printf("deque自己排:%d  vector自己排，然后再赋值回deque:%d\n", end1 - begin1, end2 - begin2);
}

//deque的结构，[]访问，偶尔用用还行，大量访问效率不及vector
//deque的中间位置insert和erase也需要考虑挪动数据，效率不高
//但是其头尾插入删除很不错

//因此stack和queue用deque做默认访问容器是比较适合的


void test_priority_queue()
{
	vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };
	/*priority_queue <int> q1;
	for (auto& e : v) q1.push(e);*/
	//priority_queue <int> q1(v.begin(), v.end()); //迭代器区间构造

   //底层是连续的物理空间，就可以直接传原生指针
	int a[] = { 3,2,7,6,0,4,1,9,8,5 };
	//默认是大堆
	//priority_queue <int> q1(a, a + sizeof(a) / sizeof(int)); //迭代器区间构造
	//小堆
	priority_queue <int,vector<int> ,greater<int>> q1(a, a + sizeof(a) / sizeof(int)); //迭代器区间构造

	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
	cout << endl;
}


int main()
{
	//Efficient1();
	//Efficient2();

	//test_priority_queue();


	return 0;
}